1. Technical Field
The present invention relates in general to data processing and in particular to performing queue recovery. Still more particularly, the present invention relates to a system, method and computer program product for performing efficient recovery of single-threaded queues.
2. Description of the Related Art
The tortoise and hare (T/H) algorithm is a well known public algorithm for efficiently detecting cycles (circular loops) in a linked list (queue) of elements. However, the T/H algorithm can not identify the queue element that caused the cycle. The T/H algorithm only detects if there is a cycle and identifies an element in the cycle. The T/H algorithm can detect cycles in many arbitrary sequences, whether in data structures or generated on the fly, notably including those in graphs and pseudo-random sequences in O(1) space. Defining a function F: ƒ: SS to be a pseudo-random function, with S a finite set of cardinality n, and define a sequence ai as: ai+1=ƒ(ai), such a sequence must cycle after at most n iterations of the pseudo-random function, because there are only n possible values for an element.
In the prior art, one way to find the length of the cycle is to store each element of the sequence and, at each iteration, look among all the stored elements for duplicates. This means that the storage requirement is O(μ+λ), where μ is the length of the cycle and λ is the length of the tail (i.e. the part of the sequence that does not cycle). Note that if two elements of the sequence are found such that ai=aj then |i−j| must be a multiple of the cycle length, because of the definition of a cycling sequence: λ+m=aλ+m+kμ. The difference of the two indices that hold equal elements is kμ, a multiple of the cycle length. The T/H cycle-finding algorithm finds such an equality by running two instances of the sequence in parallel, one twice as “fast” as the other; i.e., one instance undergoes two iterations while the other undergoes one. Then, when am=a2m, any divisor of 2m−m=m might be the length of the cycle. If m is composite, one can let the algorithm continue running until it finds more values of m for which the above equality is true, and take the greatest common divisor of the m's. This way, the list of possible μ's can be trimmed.
The best performance this algorithm can give is λ comparisons (with λ>1), because the “slow” sequence has to get at least to the beginning of the cycling part of the queue. The worst-case performance is λ+μ/2 comparisons; the slow sequence cannot get more than halfway around the loop without meeting the fast sequence. The algorithm uses O(1) storage.
To usefully apply the T/H algorithm to queue recovery applications in computing, it is important to identify the element which caused the cycle when recovering a single linked queue. The recovery operation requires the ability to repair the queue by storing an end of queue value into the element causing the cycle. This operation removes the cycle and avoids losing any of the elements on the queue.
Some operating systems contain a service, which verifies and recovers single-threaded queues. Such a utility, within the prior art, contains an algorithm that finds the element causing the cycle. The utility performs this function by examining every element on the queue. For every element on the queue, the utility scans the list from the beginning to see if the list is circular. The utility performs this operation by checking to see if the element is found on the queue at a position count before the position count of the current element being examined. While this algorithm does find the element that causes the cycle, it consumes a large amount of CPU time and the CPU time required grows exponentially as the queue gets longer. Queue verification and repair can be a CPU, memory, and wall clock time intensive operation for very long queues. The amount of checking done by the element checker routine and amount of paging needed on pageable queues affects the amount of CPU resource and elapsed time required to verify a queue.
A more efficient method, system and computer program product to verify and recover a single-threaded queue are needed.